Levenšteinin etäisyys
Levenšteinin etäisyys eli editointietäisyys (tai muokkausetäisyys[1]) on pienin määrä operaatioita, joiden avulla kahden merkkijono väliset erot voidaan poistaa. Sallittuja operaatioita ovat tavallisimmin yhden merkin lisääminen, poistaminen tai korvaaminen muulla merkillä[1]. Se on Damerau-Levenshtein-etäisyyden yksinkertaistus, josta on poistettu keino muokata kahden vierekkäisen merkin paikkojen vaihtamista keskenään[1].
Editointietäisyyden käsitteen esitti venäläinen matemaatikko Vladimir Levenštein vuonna 1965. Siitä on hyötyä sovelluksissa, joiden pitää selvittää, miten lähellä toisiaan annetut merkkijonot ovat, esimerkiksi oikeinkirjoituksen tarkistimissa tai DNA-sekvenssien vertailussa.
Editointietäisyyden erikoistapaus on Hammingin etäisyys, missä merkkijonot ovat samanpituisia ja vain merkkien korvaaminen on sallittua.
Esimerkki
[muokkaa | muokkaa wikitekstiä]Merkkijonojen urheilija ja murheilta välinen editointietäisyys on 3, koska merkkijonon muuttaminen toiseksi vaatii vähintään kolme operaatiota, esimerkiksi seuraavat:
- urheilija
- murheilija (lisättiin m)
- murheilia (poistettiin j)
- murheilta (korvattiin i t:llä)
Algoritmi
[muokkaa | muokkaa wikitekstiä]Levenšteinin etäisyyden laskeva dynaamisen ohjelmoinnin algoritmi käyttää (n + 1) × (m + 1) -kokoista matriisia, missä n ja m ovat merkkijonojen pituudet. Alla on funktion LevenshteinDistance pseudokoodi. Funktio saa syötteeksi kaksi merkkijonoa, str1, jonka pituus on lenStr1, ja str2, jonka pituus on lenStr2, ja laskee niiden välisen editointietäisyyden.
int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d on taulukko, jossa on lenStr1+1 riviä ja lenStr2+1 saraketta
declare int d[0..lenStr1, 0..lenStr2]
// i ja j käyvät läpi merkkijonot str1 ja str2
declare int i, j, cost
for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j
for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1, // poisto
d[i , j-1] + 1, // lisäys
d[i-1, j-1] + cost // korvaus
)
return d[lenStr1, lenStr2]
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b c Mustonen, Ari: [http://jultika.oulu.fi/files/nbnfioulu-201404081248.pdf Pääosin ohjaamaton sanaston poiminta rakenteettomasta tekstistä] jultika.oulu.fi.